package x.y.z;

import java.util.ArrayList;
import java.util.List;

public class LeetCode_0099 {
    private final List<TreeNode> nodes = new ArrayList<>();

    public void recoverTree(TreeNode root) {
        inorder(root);
        TreeNode first = null;
        TreeNode last = null;

        for (int i = 0; i < nodes.size() - 1; i++) {
            if (nodes.get(i + 1).val < nodes.get(i).val) {
                last = nodes.get(i + 1);
                if (first == null) {
                    first = nodes.get(i);
                } else {
                    break;
                }
            }
        }

        if (first != null && last != null) {
            int temp = first.val;
            first.val = last.val;
            last.val = temp;
        }
    }

    private void inorder(TreeNode root) {
        if (root != null) {
            inorder(root.left);
            nodes.add(root);
            inorder(root.right);
        }
    }
}
